Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Constraints:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
-10^4 <= target <= 10^4
My Solution
This is an application of binary search. The only detail is what to return when target is not in nums. We can use Example 2 as an example. In binary search for this test case, start will be 0 and end would be 3. At the end of the first iteration, start and end both would be 0. At the end of the second iteration, start would be 1 and end would be 0. This is where we stop. We want to return 1 here since that is where the number should be inserted. Using this example, we should return start if the number is not found because at the end of binary search start will always be greater than end and that is the position where we want to add the element.
Time complexity is O(log n) because of binary search. Space complexity is O(1).
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int start = 0;
int end = n-1;
while (start <= end) {
int mid = start + (end-start)/2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
start = mid+1;
}
else {
end = mid-1;
}
}
return start;
}
}